/*
 * @lc app=leetcode.cn id=456 lang=typescript
 *
 * [456] 132 模式
 */

// @lc code=start
function find132pattern(nums: number[]): boolean {
  const m = nums.length;
  // 保存每个元素左边的最小值
  const l = new Array(m).fill(Number.POSITIVE_INFINITY);
  for (let i = 1; i < m; i++) {
    l[i] = Math.min(nums[i - 1], l[i - 1]);
  }

  const stack: number[] = [];
  // 倒叙遍历，去找小于当前元素的第一个值，也就是132中的2
  for (let i = m - 1; i >= 0; i--) {
    let r: number = Number.NEGATIVE_INFINITY;
    while (stack.length && nums[i] > stack[stack.length - 1]) {
      r = stack.pop();
    }
    if (l[i] < r && l[i] < nums[i] && r < nums[i]) return true;
    stack.push(nums[i]);
  }

  return false;
}
// @lc code=end
